package Offer.offer;

import util.SwapUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 最小的K个数
 * @author leiwenkang
 * @date 2020/4/9
 */
public class Test30最小的K个数 {
    public static void main(String[] args) {
        int []array={4,5,1,-6,9,7,3,8};
        List<Integer>  result = getMinNumbers(array,3);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }

    //基于堆排序
    public static List<Integer> getMinNumbers(int[] array, int k) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("数组非法！");
        }
        //构建K个元素的最大堆
        for (int i = k / 2 - 1; i >= 0; i--) {
            adjust(array, i, k - 1);
        }

        for (int i = k; i < array.length - 1; i++) {
            if (array[i] < array[0]) {
                SwapUtil.swap(array, 0, i);
                adjust(array, 0, k - 1);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(array[i]);
        }
        return result;
    }

    private static void adjust(int[] array, int index, int end) {
        for (int i = 2 * index + 1; i <= end ; i = 2 * i + 1) {
            if (i < end && array[i] < array[i + 1]) {
                i++;
            }
            if (array[i] < array[index]) {
                break;
            }
            SwapUtil.swap(array, i, index);
            index = i;
        }

    }


    public static List<Integer> getMinNumbers2(int[] array, int k) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("数组非法！");
        }
        int low = 0;
        int high = array.length - 1;
        int pos = partition(array, low, high);
        while (pos != k - 1) {
            if (pos < k - 1) {
                pos = partition(array, pos + 1, high);
            } else {
                pos = partition(array, low, pos - 1);
            }
        }
        //收集数组的前k-1个元素
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(array[i]);
        }
        return result;
    }

    //基于partition函数
    private static int partition(int[] array, int low, int high) {
        int value = array[low];
        while (low < high) {
            while (low < high && array[high] >= value) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= value) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = value;
        return high;
    }
}
